/*
给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

// 2020.8.12 town
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.empty()){
            return intervals;
        }
        sort(intervals.begin(),intervals.end(),cmp);
        /*
        for(int i=0;i<intervals.size();i++){
            cout<<intervals[i][0]<<" "<<intervals[i][1]<<endl;
        }
        */
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>res[res.size()-1][1]){
                res.push_back(intervals[i]);
            }else{
                if(intervals[i][1]>res[res.size()-1][1]){
                    res[res.size()-1][1]=intervals[i][1];
                }
            }
        }
        return res;
    }

private:
    static bool cmp(vector<int>& i, vector<int>& j){
        if(i[0]!=j[0]){
            return i[0]<j[0];
        }
        return i[1]<j[1];
    }
};